#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

//Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
	{
	}
};

class Solution {
        pair<int, int> min_cover(TreeNode *root)
        {
                if(root == nullptr){
                        return {0, 0};
                }
                pair<int, int> info(1, 0);
                pair<int, int> linfo = min_cover(root->left);
                pair<int, int> rinfo = min_cover(root->right);
                info.first = 1 + min(linfo.first, linfo.second) + min(rinfo.first, rinfo.second);
                info.second += linfo.first + rinfo.first;
                return info;
        }
    public:
	int minCameraCover(TreeNode *root)
	{
                if(root->left == nullptr && root->right == nullptr){
                        return 1;
                }
                pair<int, int> info = min_cover(root);
                return min(info.first, info.second);
	}
};

int main()
{
        TreeNode root(1);
        root.left = new TreeNode(2);
        cout<<Solution().minCameraCover(&root)<<endl;
	return 0;
}
